class Graph(object):
    """Pure virtual class for graph"""
    def addRandomVertex():
        pass
    def getCoverage():
        pass

import random

class OneDimensionalGraph(Graph):
    def __init__(self, number_vertices=None, radius=.5):
        self.__vertices = []
        self.__leftmost = 0.
        self.__rightmost = 0.
        self.__radius = radius
        if number_vertices is not None:
            for n in range(number_vertices):
                self.addRandomVertex()

    def addRandomVertex(self):
        if len(self.__vertices) == 0:
            self.__vertices.append(0.)
            return
        # Generate new vertex
        left_bound = self.__leftmost - self.__radius
        right_bound = self.__rightmost + self.__radius
        new_vertex = random.uniform(left_bound, right_bound)
        # Update state
        self.__vertices.append(new_vertex)
        if new_vertex < self.__leftmost:
            self.__leftmost = new_vertex
        elif new_vertex > self.__rightmost:
            self.__rightmost = new_vertex

    def getCoverage(self):
        if len(self.__vertices) == 0:
            return 0
        else:
            return self.__rightmost - self.__leftmost + 2 * self.__radius

    def getVertices(self):
        return sorted(self.__vertices)

    def findConnectedDominatingSet(self):
        if len(self.__vertices) == 0:
            return []
        self.__vertices.sort()

        # Initialize dominating set
        first_dominating_vertex_index = 0
        for i, vertex in enumerate(self.__vertices):
            if self.__dist(vertex, self.__leftmost) > self.__radius:
                first_dominating_vertex_index = i-1
                break
        dominating_set = [self.__vertices[first_dominating_vertex_index]]

        for i in range(first_dominating_vertex_index + 1, len(self.__vertices) - 1):
            if self.__dist(self.__vertices[i], dominating_set[-1]) <= self.__radius and \
               self.__dist(self.__vertices[i+1], dominating_set[-1]) > self.__radius:
                dominating_set.append(self.__vertices[i])

        return dominating_set

    def getRadius(self):
        return self.__radius

    def __dist(self, first_v, second_v):
        return abs(first_v - second_v)

class OneDimensionalGraphPeerAttachment(Graph):
    def __init__(self, number_vertices=None, radius=.5):
        self.__vertices = []
        self.__leftmost = 0.
        self.__rightmost = 0.
        self.__radius = radius
        if number_vertices is not None:
            for n in range(number_vertices):
                self.addRandomVertex()

    def addRandomVertex(self):
        if len(self.__vertices) == 0:
            self.__vertices.append(0.)
            return
        # Generate new vertex
        left_bound = self.__leftmost - self.__radius
        right_bound = self.__rightmost + self.__radius
        peer = random.choice(self.__vertices)
        new_vertex = random.uniform(peer - self.__radius, peer + self.__radius)
        # Update state
        self.__vertices.append(new_vertex)
        if new_vertex < self.__leftmost:
            self.__leftmost = new_vertex
        elif new_vertex > self.__rightmost:
            self.__rightmost = new_vertex

    def getCoverage(self):
        if len(self.__vertices) == 0:
            return 0
        else:
            return self.__rightmost - self.__leftmost + 2 * self.__radius

    def getVertices(self):
        return sorted(self.__vertices)

    def findConnectedDominatingSet(self):
        if len(self.__vertices) == 0:
            return []
        self.__vertices.sort()
        # if len(self.__vertices) < 3:
        #     return [self.__vertices[0]]
        # if len(self.__vertices) == 3:
        #     return [self.__vertices[1]]

        # Initialize dominating set
        first_dominating_vertex_index = 0
        for i, vertex in enumerate(self.__vertices):
            if self.__dist(vertex, self.__leftmost) > self.__radius:
                first_dominating_vertex_index = i-1
                break
        dominating_set = [self.__vertices[first_dominating_vertex_index]]

        for i in range(first_dominating_vertex_index + 1, len(self.__vertices) - 1):
            if self.__dist(self.__vertices[i], dominating_set[-1]) <= self.__radius and \
               self.__dist(self.__vertices[i+1], dominating_set[-1]) > self.__radius:
                dominating_set.append(self.__vertices[i])

        return dominating_set

    def getRadius(self):
        return self.__radius

    def __dist(self, first_v, second_v):
        return abs(first_v - second_v)

class TwoDimensionalGraphCellularModel(Graph):
    """
    Each node covers (2*cell_radius + 1) x (2*cell_radius + 1) cells
    """
    def __init__(self, number_vertices=None, cellular_radius=1, cross=False):
        self.__cells = set()
        self.__cellular_radius = cellular_radius
        self.__cross = cross
        if number_vertices is not None:
            for n in range(number_vertices):
                self.addRandomVertex()

    def addRandomVertex(self):
        if len(self.__cells) == 0:
            # init cells
            neighbourhood = self.__generateNeighbourhood((0,0))
            for neigh in neighbourhood:
                self.__cells.add(neigh)
            return
        # Generate new vertex and neighbourhood
        random_cell = random.choice(list(self.__cells))
        new_neighbourhood = self.__generateNeighbourhood(random_cell)
        # Update state of cellular graph
        for neigh in new_neighbourhood:
            self.__cells.add(neigh)

    def getCoverage(self):
        return len(self.__cells) / float(2*self.__cellular_radius + 1)**2

    def getBorder(self):
        # check if cell is surrounded by other cells
        border = []
        if self.__cross:
            for c in self.__cells:
                for n in self.__generateNeighbourhood(c):
                    if not n in self.__cells:
                        border.append(c)
                        break
        else:
            return []  # TODO
        return border

    def getNumberOfCells(self):
        return len(self.__cells)

    def getCells(self):
        return list(self.__cells)

    def __generateNeighbourhood(self, cell_coords):
        # cell_coords is a 2-tuple of (x,y) coordinates
        x0, y0 = cell_coords
        cl = self.__cellular_radius
        neigh = []
        if self.__cross:
            # 4 neighbours
            neigh.append( (x0+1,y0) )
            neigh.append( (x0-1,y0) )
            neigh.append( (x0,y0+1) )
            neigh.append( (x0,y0-1) )
            pass
        else:
            for i in range(-cl, cl+1):
                for j in range(-cl, cl+1):
                    neigh.append( (x0+i, y0+j) )
        return neigh
